//
//  PalindromePairs.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/13.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  336. 回文对

import UIKit

/*
 336. 回文对
 给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

 示例 1：

 输入：["abcd","dcba","lls","s","sssll"]
 输出：[[0,1],[1,0],[3,2],[2,4]]
 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
 
 示例 2：

 输入：["bat","tab","cat"]
 输出：[[0,1],[1,0]]
 解释：可拼接成的回文串为 ["battab","tabbat"]
 
 */

/*
 思路和算法
 
 假设存在两个字符串 s1 和 s2 满足 s1+s2 是一个回文串，两个字符串长度分别记做 len1 和 len2，则有一下三种情况
 1. len1 = len2 此时 s1 是 s2 的翻转。
 2. len1 > len2 此时可以将 s1 拆分成左右 t1 和 t2，其中 t1 是 s2 的翻转，t2 是一个回文串。
 2. len1 < len2 此时可以将 s2 拆分成左右 t1 和 t2，其中 t2 是 s1 的翻转，t1 是一个回文串。
 
 这样，对于每一个字符串，我们令其为 s1 和 s2 中比较长那一个，然后找到可能和它构成的回文串的字符串即可。
 
 具体来说，我们枚举每一个字符串k，令其等于s1和s2较长那一个，那么k可以被拆分成 t1 和 t2
 1.当 t1 是回文串时，符合情况3，我们只需要查询给定的字符串序列中是否包含 t2 的翻转
 1.当 t2 是回文串时，符合情况2，我们只需要查询给定的字符串序列中是否包含 t1 的翻转
 
 也就是说，我们要枚举字符串 k 的每一个前缀和后缀，判断其是否为回文串。如果是回文串，我们就查询其剩余部分的翻转是否在给定的字符串序列中出现即可。
 注意空串也是回文串。

 tip:我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。
 
 */

class PalindromePairs: NSObject {
    
    var cacherReversedString:[String:Int] = [:]
    
    func palindromePairs(_ words: [String]) -> [[Int]] {
     
        //将所有字符串的倒序存入哈希表
        words.enumerated().forEach { (index, str) in
            cacherReversedString[String(str.reversed())] = index
        }
        
        let n = words.count
        var result = [[Int]]()
        
        for i in 0 ..< n {
            let word = words[i]
            let m = word.count
            if m == 0 {
                continue
            }
            for j in 0 ... m{
                if self.isPalindrome(word, j, m-1) {
                    let leftId = self.findWord(word, 0, j-1)
                    if leftId != -1 && leftId != i {
                        result.append([i,leftId])
                    }
                }
                if j != 0 && self.isPalindrome(word, 0, j-1) {
                    let rightId = self.findWord(word, j, m-1)
                    if rightId != -1 && rightId != i {
                        result.append([rightId,i])
                    }
                }
            }
        }
        
        return result
    }
    
    //判断字符串的某个索引区间内是否是回文串
    func isPalindrome(_ string: String, _ left: Int, _ right: Int) -> Bool{

        let array = Array(string)
        let len = right - left + 1
        
        for i in 0 ..< len/2 {
            if array[left+i] != array[right-i] {
                return false
            }
        }
        return true
    }
    
    func findWord(_ string:String, _ left: Int, _ right: Int) -> Int{
        if string.count == 1 || string.count == 0 {
            return cacherReversedString[string] ?? -1
        }
        
        let beginIndex = string.index(string.startIndex, offsetBy: left)
        let endIndex = string.index(string.startIndex, offsetBy: right)
        let str = string[beginIndex...endIndex]
        
        return cacherReversedString[String(str)] ?? -1
    }
    
    
    
    
    
    
    
    
    func palindromePairs2(_ words: [String]) -> [[Int]] {
        //将所有字符串的倒序存入哈希表
        words.enumerated().forEach { (index, str) in
            cacherReversedString[String(str.reversed())] = index
        }
        
        var result = [[Int]]()
        
        for i in 0 ..< words.count {
            let curWord = words[i]
            // 如果有空字符串的话
            if self.isPalindrome2(curWord) && cacherReversedString[""] != nil && curWord != "" {
                result.append([cacherReversedString[""]!, i])
            }
            for j in 0 ..< curWord.count {
                let left = String(curWord.prefix(j)), right = String(curWord.suffix(curWord.count - j))
                //左边是回文，右边是翻转
                if self.isPalindrome2(left) && cacherReversedString[right] != nil && cacherReversedString[right] != i {
                    result.append([cacherReversedString[right]!, i])
                }
                // 右边是回文，左边是翻转
                if self.isPalindrome2(right) && cacherReversedString[left] != nil && cacherReversedString[left] != i {
                    result.append([i,cacherReversedString[left]!])
                }
            }
        }
        
        /*
        for (i,s) in words.enumerated() {
            if s.isEmpty{
                cacherReversedString.forEach { (element) in
                    if self.isPalindrome2(element.key) && (i != element.value){
                        result.append([i,element.value])
                    }
                }
                
            }
            
            for i in 0 ..< s.count{
                let middleIndex = s.index(s.startIndex, offsetBy: i)
                let firstPart = String(s[..<middleIndex])
                let secondPart = String(s[middleIndex...])
                if self.isPalindrome2(firstPart), let j = cacherReversedString[secondPart], i != j {
                    result.append([j,i])
                }
                if self.isPalindrome2(secondPart), let j = cacherReversedString[firstPart], i != j {
                    result.append([i,j])
                }
            }
        }*/
        
        return result
    }
    
    func isPalindrome2(_ string: String) -> Bool{
        return string == String(string.reversed())
    }
}

